package 寒假刷题;

import java.util.*;

public class RandomizedSet {
    List<Integer> list;
    Map<Integer,Integer> map;
    Random random;
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
         if (map.containsKey(val))
             return false;
         list.add(val);
         map.put(val,list.size()-1);
         return true;
    }

    public boolean remove(int val) {
         if (!map.containsKey(val))
             return false;
        Integer last = list.get(list.size() - 1);
        Integer idx = map.get(val);
        list.set(idx,last);
        list.remove(list.size()-1);
        map.put(last,idx);
        map.remove(val);
        return true;
    }

    public int getRandom() {
         return list.get(random.nextInt(list.size()));
    }
}
